0% completed
Problem Statement
You are given a 2D list called descriptions. Each element in descriptions represents a relationship in a binary tree. The element descriptions[i] = [parenti, childi, isLefti] tells us that parenti is the paent of childi. The isLefti value can be either 1 or 0:
- If isLefti is 1,
childiis the left child of parenti. - If isLefti is 0, childi is the right child of parenti.
Build this binary tree from the given description and return its root node.
Each node in the binary tree has a unique value.
Examples
Example 1
- Input: descriptions =
[[1, 2, 1], [1, 3, 0], [2, 4, 1]] - Expected Output: [1, 2, 3, 4]
- Justification: Node 1 is the root, 2 is the left child, 3 is the right child. Node 2 has 4 as its left child.
Example 2:
- Input: descriptions =
[[10, 5, 1], [10, 15, 0], [5, 3, 1], [15, 20, 0]] - Expected Output: [10,5,15,3,null,null,20]
- Justification: Node 10 is the root, with 5 as the left child and 15 as the right child. Node 5 has 3 as its left child, and 15 has 20 as its right child.
Example 3:
- Input: descriptions =
[[5, 3, 1], [5, 7, 0], [3, 2, 1], [3, 4, 0]] - Expected Output: [5,3,7,2,4]
- Justification: Node 5 is the root with 3 as the left child and 7 as the right child. Node 3 has 2 as the left child and 4 as the right child.
Constraints:
- 1 <= descriptions.length <= 104
- descriptions[i].length == 3
- 1 <= parenti, childi <= 105
- 0 <= isLefti <= 1
- The binary tree described by descriptions is valid.
Solution
To solve this problem, we create a map to store nodes by their values. Each time we encounter a parent or child value, we ensure that a corresponding node exists in this map (by checking if the node already exists and creating it if it doesn't). We also maintain a set of child nodes to track which nodes are children in the tree. After processing the entire input, the root node will be the only node not found in this set of children (because every other node is a child of some other node). We then return this root node to represent the complete binary tree. This approach is effective because it handles all necessary tasks (node creation, tree construction, and root detection) in a single pass through the input, making it efficient.
Step-by-Step Algorithm
- Initialize Structures:
- Create a map (
nodeMap) to store nodes using their values as keys. - Create a set (
children) to keep track of child nodes.
- Create a map (
- Iterate through descriptions:
- For each description:
- Extract the values of
parent,child, andisLeft. - Create or fetch parent node:
- Check if
parentexists innodeMap. If not, create a newTreeNodeforparentand put it innodeMap.
- Check if
- Create or fetch child node:
- Check if
childexists innodeMap. If not, create a newTreeNodeforchildand put it innodeMap.
- Check if
- Add the child to the parent:
- If
isLeft == 1, setparent.leftto the child. - If
isLeft == 0, setparent.rightto the child.
- If
- Record the child node:
- Add the
childvalue to thechildrenset.
- Add the
- Extract the values of
- For each description:
- Determine the root:
- Iterate through the keys (node values) in
nodeMap. The node whose value is not in thechildrenset is the root, since it is not a child of any other node.
- Iterate through the keys (node values) in
- Return the root node:
- Return the node found in the previous step as the root of the binary tree.
Algorithm Walkthrough
We will now walk through the algorithm using the input:
descriptions = [[10, 5, 1], [10, 15, 0], [5, 3, 1], [15, 20, 0]]
-
Initialize
nodeMapandchildren:nodeMap = {}(empty map)children = {}(empty set)
-
Processing each description:
- First description
[10, 5, 1]:- Parent is
10, child is5, andisLeft == 1. 10is not innodeMap, so we create a node for10:TreeNode(10).5is not innodeMap, so we create a node for5:TreeNode(5).- Set
10.left = 5. - Add
5tochildren:children = {5}.
- Parent is
- Second description
[10, 15, 0]:- Parent is
10, child is15, andisLeft == 0. 10is already innodeMap, so no need to create a new node.15is not innodeMap, so we create a node for15:TreeNode(15).- Set
10.right = 15. - Add
15tochildren:children = {5, 15}.
- Parent is
- Third description
[5, 3, 1]:- Parent is
5, child is3, andisLeft == 1. 5is already innodeMap.3is not innodeMap, so we create a node for3:TreeNode(3).- Set
5.left = 3. - Add
3tochildren:children = {3, 5, 15}.
- Parent is
- Fourth description
[15, 20, 0]:- Parent is
15, child is20, andisLeft == 0. 15is already innodeMap.20is not innodeMap, so we create a node for20:TreeNode(20).- Set
15.right = 20. - Add
20tochildren:children = {3, 5, 15, 20}.
- Parent is
- First description
-
Find the root:
- We check the keys in
nodeMap:10,5,15,3,20. - The value
10is not inchildren, so10is the root.
- We check the keys in
-
Return the root:
- The root node is
TreeNode(10).
- The root node is
Code
Complexity Analysis
Time Complexity
- Tree Construction: For each description, we either create or retrieve the parent and child nodes from a hashmap, which is an
operation. To traverse ndescriptions, the overall time complexity is.
Therefore, the total time complexity of the solution is
Space Complexity
- Tree Construction: We store all nodes in a hashmap and a set. The space required for this is proportional to the number of nodes,
.
Thus, the space complexity of the algorithm is
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity